// https://leetcode.cn/problems/subtree-of-another-tree/
// Created by ade on 2022/8/9.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    //
    /*
     * 字符串投机取巧的的方式 效率较低
     *
    bool isSubtree(TreeNode *root, TreeNode *subRoot) {
        string sub = "";
        string all = "";
        show(root, all);
        show(subRoot, sub);
        return all.find(sub) != string::npos;
    }


    void show(TreeNode *node, string &res) {
        if (!node) {
            res += "null";
            return;
        }
        res += "-" + to_string(node->val);
        show(node->left, res);
        show(node->right, res);
    }
     * */

    bool flag = false;
    vector<TreeNode *> res;
    int allHeight = 0, subHeight = 0;

    bool isSubtree(TreeNode *root, TreeNode *subRoot) {
        dfs(root, subRoot);
        for (auto node : res) {
            if (compare(node, subRoot)) return true;
        }
        return false;
    }

    // 比较两个二叉树是否相等
    bool compare(TreeNode *p, TreeNode *q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p == nullptr || q == nullptr) {
            return false;
        } else if (p->val != q->val) {
            return false;
        } else {
            return compare(p->left, q->left) && compare(p->right, q->right);
        }
    }

    void dfs(TreeNode *root, TreeNode *subRoot) {
        if (!root) return;
        if (allHeight - index == subHeight && root->val == subRoot->val) {
            res.push_back(root);
        }
        dfs(root->left, subRoot);
        dfs(root->right, subRoot);
    }

};

int main() {
    Solution so;
    TreeNode *h1 = so.init();
    auto res = so.levelOrder(h1);
    for (auto items : res) {
        for (auto i : items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}